package com.dp;

import java.util.Arrays;
import java.util.Comparator;

public class Solution16 {
    int count = 0;
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if ((sum+target)%2 !=0) return 0;
        int x = (sum+target)>>1;
        backtracking(nums,0,x,0);
        return count;
    }

    public void backtracking(int[] nums,int index,int x,int sum) {
        if (sum == x) {
            count++;
        }
        for (int i = index; i < nums.length; i++) {
            sum += nums[i];
            backtracking(nums,i+1,x,sum);
            sum -= nums[i];
        }
    }

    public int findTargetSumWays1(int[] nums, int target) {
        int sum = 0;
        for (int x : nums) {
            sum += x;
        }
        if (target<0 && -sum>target) return 0;
        if ((sum+target)%2 != 0) return 0;
        int x = (sum+target)>>1;
        x = x<0?-x:x;
        int[] dp = new int[x+1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = x; j >= nums[i]; j--) {
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[x];
    }

}
